import java.util.ArrayList;
import java.util.List;

public class Generate {
    // 杨辉三角
    // https://leetcode.cn/problems/pascals-triangle/?envType=study-plan-v2&envId=top-100-liked
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> prev = null;
        for (int i = 0; i < numRows; i++) {
            List<Integer> path = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    path.add(1);
                } else {
                    path.add(prev.get(j-1) + prev.get(j));
                }
            }
            prev = path;
            ret.add(path);
        }
        return ret;
    }
}
